package com.vint.leetcode;

import com.vint.common.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/*
 *
 */
public class Leetcode637 {
    public List<Double> averageOfLevels(TreeNode root) {
    	if(null==root)return null;
        Queue<TreeNode> queue = new LinkedList<>();
        List<Double> ret = new ArrayList<>();
        queue.add(root);
        int level = 1;
        long sum = 0;
        while(!queue.isEmpty()){
            int t = level;
            int nexLevel = 0;
            while (level--!=0){
                TreeNode peek = queue.peek();
                if(peek.left!=null) {
                    queue.add(peek.left);
                    nexLevel++;
                }
                if(null!=peek.right){
                    queue.add(peek.right);
                    nexLevel++;
                }
                sum += queue.poll().val;
            }
            ret.add(sum * 1.0 / t);
            level = nexLevel;
            sum = 0;
        }
        return ret;
    }


    public static void main(String[] args) {
        //TreeNode root = TreeNode.mockSpecific1();
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(2);
        root.left.left = new TreeNode(2);
        root.left.left.left = new TreeNode(-2);
        root.right= new TreeNode(-3);
        Leetcode637 leetcode637 = new Leetcode637();
        List<Double> ret =  leetcode637.averageOfLevels(root);
        System.out.println("success!");
    }
  }
